Programmation fonctionnelle - TD 2 : Algorithmes combinatoires

1. Parties d’un ensemble

1.1 Contrat

(*
parties : 'a list -> 'a list list
Paramètres : l - une liste quelconque d'éléments
Résultat : une liste de listes, dont les 2^(List.length l) éléments 
sont les sous-listes de l. 
Si les éléments de l sont différents, les listes éléments du résultat
seront différentes aussi, et formeront les parties de l.
*)

1.2 Raffinage fonctionnel

Exercice 1 : Donner une formulation récursive comptant le nombre de parties d’un ensemble de cardinal n.

[] -> []                           1 partie
[e1] -> [e1],[]                    2 parties (soit je prend e1, soit je ne le prends pas) 
[e1,e2] -> [e1,e2],[e1],[e2],[]    4 parties (je peux prendre e2 ou non pour l'ajouter aux parties calculées au niveau n-1)

Ainsi, n éléments -> 2^n parties

Exercice 2 :

• Ecrire la fonction ajout, qui à partir d’un élément $e$ et d’ensembles $\{E_1, \ldots,E_n\}$ renvoie l’enemble $\{E_1,\{e\} \cup E_1, \ldots, \{e\} \cup E_n\}$.

(*
Contrat ajout : 'a -> 'a list list -> 'a list list
Paramètres :
    - e : 'a - élément à ajouter à chaque ensemble
    - parties : 'a list list - liste des parties
Résultat : 'a list list - 
    liste des parties en ayant pris en compte l'ajout de l'élément e
*)
let ajout e parties = List.flatten (List.map (fun p -> [p;e::p]) parties)

(* OU *)
let ajout e parties = parties@(List.map (fun p -> e::p) parties)

• Ecrire la fonction parties, qui renvoie l’ensemble des parties d’un ensemble.

(*
Contrat parties : 'a list -> 'a list list
Paramètres : 
    - l : 'a list - un ensemble
Résultat : 'a list list - parties de l'ensemble l
*)
let rec parties l = 
    match l with
    | [] -> [[]]
    | e::r -> ajout e (parties r)
    
(* OU *)
let parties l = fold_right ajout l [[]]

2. Permutations d’une liste

2.1 Contrat

(*
permutations : 'a list -> 'a list list
Paramètres : l - une liste quelconque d'éléments
Résultat : une liste de listes, dont les (List.length l)! éléments ont la même
longueur que l. Si les éléments de l sont différents, les listes éléments du
résultat seront différentes aussi, et formeront les permutations de l.
*)

2.2 Raffinage fonctionnel

Exercice 3 : Donner une formulation récursive comptant le nombre de permutations d’un ensemble de taille n.

[] -> []                                            1 permutation
[e1] -> [e1]                                        1 permutation
[e1;e2] -> [e1;e2],[e2;e1]                          2 permutations (on a inséré e2 à toutes les positions possibles)
[e1;e2;e3] -> [e3;e1;e2],[e1;e3;e2],[e1;e2;e3],     6 permutations (on a inséré e3 à toutes les positions possibles pour chaque ensemble du niveau précédent)
              [e3;e2;e1],[e2;e3;e1],[e2;e1;e3]

Exercice 4 :

• Ecrire la fonction insertions, qui insère un élément à toutes les positions d’une liste.

(*
Contrat insertions : 'a -> 'a list -> 'a list list - 
    Insère l'élément à toutes les possitions possibles de l
Paramètres :
    - e : 'a - élément à insérer
    - l : 'a list
Résultat : 'a list list - 
    liste de toutes les possibilités d'insertion de e dans l
*)
let rec insertions e l =
    match l with
    | [] -> [[e]]
    | t::q -> (e::l) :: (List.map (fun x -> t::x) (insertions e q))

• Ecrire la fonction permutations, qui renvoie l’ensemble des permutations d’un ensemble.

(*
Contrat permutations : 'a list -> 'a list list - 
    Calcule toutes les permutations d'un ensemble
Paramètres :
    - l : 'a list - l'ensemble dont on va calculer les permutations
Résultat : 'a list list - Ensemble des permutations de l
*)
let rec permutations l =
    match l with
    | [] -> [[]]
    | t::q -> List.flatten (List.map (fun x -> insertions t x) (permutations q))

3. Combinaisons

3.1 Contrat

(*
combinaisons : 'a list -> int -> 'a list list
Paramètres :
    - l : 'a list - une liste quelconque d'éléments supposés différents
    - k : int - le nombre d'éléments distincts à tirer
Résultat : une liste de combinaisons. Chaque combinaison est elle-même une liste
d'éléments, dont les éléments sont ceux de l.
*)

3.2 Raffinage fonctionnel

Exercice 5 : Donner une formulation récursive comptant le nombre de combinaisons de k éléments d’un ensemble à n éléments.

C(k,0) = 1 -> [[]]
C(0,n) = 0 -> []
C(k,n) = C(k-1,n-1) + C(k,n-1) -> soit je prend le nouvel élément, soit je ne le prend pas

Exercice 6 : Ecrire la fonction combinaisons (contrat + code + tests).

(*
Contrat combinaisons : 'a list -> int -> 'a list list - 
    Calcule toutes les combinaisons de k éléments d'un ensemble à n éléments
Paramètres :
    - l : 'a list - ensemble des éléments
    - k : int - nombre d'éléments dont on veut calculer les combinaisons
Résultat : 'a list list - Toutes les parties de l à k éléments
*)
let rec combinaisons l k =
    match (l,k) with
    | (_,0) -> [[]]
    | ([],_) -> []
    | (t::q,_) -> (List.map (fun x -> t::x) (combinaisons q (k-1))) @ (combinaisons q k)
    
let%test _ = combinaisons ['c';'a';'c';'a'] 0 = [[]]
let%test _ = combinaisons [] 69 = []
let%test _ = combinaisons ['t';'g'] 1 = [['t'];['g']]
let%test _ = combinaisons ['f';'t';'g'] 2 = [['f';'t'];['f';'g'];['t';'g']]